package com.desheng.bigdata.ds.heap;

/**
 * @Description TODO
 * @Author deshenglijun
 * @Date 2020/5/25 21:25
 * @Version 1.0
 */
public class HeapSort {
    /*
    判断索引i位置的元素是否小于索引j位置的元素
 */
    public static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }
    //交换索引i和索引j位置的元素
    public static void exchange(Comparable[] heap, int i, int j) {
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    private static void createHeap(Comparable[] array, Comparable[] heap) {
        //1.把array中的数据拷贝到heap中，从heap的1索引处开始填充
        System.arraycopy(array, 0, heap, 1, array.length);
        //2.从heap索引的一半处开始倒叙遍历，对得到的每一个元素做下沉操作
        for(int i = (heap.length - 1) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }

    //在heap堆中，对target处的元素做下沉，范围是0~range
    private static void sink(Comparable[] heap, int target, int range){
        //没有子结点了
        while (2 * target <= range) {
            //1.找出target结点的两个子结点中的较大值
            int max = 2 * target;
            if(max + 1 <= range) {
                //存在右子节点
                if(less(heap, max, max + 1)) {
                    max = max + 1;
                }
            }
            //2.如果当前结点的值小于子结点中的较大值，则交换
            if(less(heap, target, max)) {
                exchange(heap, target, max);
            }
            //3.更新target的值
            target = max;
        }
    }

    //对source数组中的数据从小到大排序
    public static void sort(Comparable[] array) {
        //1.创建一个比原数组大1的数组
        Comparable[] heap = new Comparable[array.length + 1];
        //2.构造堆
        createHeap(array,heap);
        //3.堆排序
        //3.1定义一个变量，记录heap中未排序的所有元素中最大的索引
        int index = heap.length - 1;
        while (index != 1) {
            //3.2交换heap中索引1处的元素和N处的元素
            exchange(heap, 1, index);
            index--;
            //3.3对索引1处的元素在0~N范围内做下沉操作
            sink(heap, 1, index);
        }
        //4.heap中的数据已经有序，拷贝到source中
        System.arraycopy(heap, 1, array, 0, array.length);
    }

}
